"use strict";
/*
 * Copyright (c) 2022 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
const CRYPTO_NUMBER_0XFFFFFF = 0xffffff;
const CRYPTO_NUMBER_0XEFCAFE = 0xefcafe;
const CRYPTO_NUMBER_0 = 0;
const CRYPTO_NUMBER_1 = 1;
const CRYPTO_NUMBER_2 = 2;
const CRYPTO_NUMBER_3 = 3;
const CRYPTO_NUMBER_5 = 5;
const CRYPTO_NUMBER_7 = 7;
const CRYPTO_NUMBER_11 = 11;
const CRYPTO_NUMBER_13 = 13;
const CRYPTO_NUMBER_17 = 17;
const CRYPTO_NUMBER_19 = 19;
const CRYPTO_NUMBER_23 = 23;
const CRYPTO_NUMBER_29 = 29;
const CRYPTO_NUMBER_31 = 31;
const CRYPTO_NUMBER_37 = 37;
const CRYPTO_NUMBER_41 = 41;
const CRYPTO_NUMBER_43 = 43;
const CRYPTO_NUMBER_47 = 47;
const CRYPTO_NUMBER_53 = 53;
const CRYPTO_NUMBER_59 = 59;
const CRYPTO_NUMBER_61 = 61;
const CRYPTO_NUMBER_67 = 67;
const CRYPTO_NUMBER_71 = 71;
const CRYPTO_NUMBER_73 = 73;
const CRYPTO_NUMBER_79 = 79;
const CRYPTO_NUMBER_83 = 83;
const CRYPTO_NUMBER_89 = 89;
const CRYPTO_NUMBER_97 = 97;
const CRYPTO_NUMBER_101 = 101;
const CRYPTO_NUMBER_103 = 103;
const CRYPTO_NUMBER_107 = 107;
const CRYPTO_NUMBER_109 = 109;
const CRYPTO_NUMBER_113 = 113;
const CRYPTO_NUMBER_127 = 127;
const CRYPTO_NUMBER_131 = 131;
const CRYPTO_NUMBER_137 = 137;
const CRYPTO_NUMBER_139 = 139;
const CRYPTO_NUMBER_149 = 149;
const CRYPTO_NUMBER_151 = 151;
const CRYPTO_NUMBER_157 = 157;
const CRYPTO_NUMBER_163 = 163;
const CRYPTO_NUMBER_167 = 167;
const CRYPTO_NUMBER_173 = 173;
const CRYPTO_NUMBER_179 = 179;
const CRYPTO_NUMBER_181 = 181;
const CRYPTO_NUMBER_191 = 191;
const CRYPTO_NUMBER_193 = 193;
const CRYPTO_NUMBER_197 = 197;
const CRYPTO_NUMBER_199 = 199;
const CRYPTO_NUMBER_211 = 211;
const CRYPTO_NUMBER_223 = 223;
const CRYPTO_NUMBER_227 = 227;
const CRYPTO_NUMBER_229 = 229;
const CRYPTO_NUMBER_233 = 233;
const CRYPTO_NUMBER_239 = 239;
const CRYPTO_NUMBER_241 = 241;
const CRYPTO_NUMBER_251 = 251;
const CRYPTO_NUMBER_257 = 257;
const CRYPTO_NUMBER_263 = 263;
const CRYPTO_NUMBER_269 = 269;
const CRYPTO_NUMBER_271 = 271;
const CRYPTO_NUMBER_277 = 277;
const CRYPTO_NUMBER_281 = 281;
const CRYPTO_NUMBER_283 = 283;
const CRYPTO_NUMBER_293 = 293;
const CRYPTO_NUMBER_307 = 307;
const CRYPTO_NUMBER_311 = 311;
const CRYPTO_NUMBER_313 = 313;
const CRYPTO_NUMBER_317 = 317;
const CRYPTO_NUMBER_331 = 331;
const CRYPTO_NUMBER_337 = 337;
const CRYPTO_NUMBER_347 = 347;
const CRYPTO_NUMBER_349 = 349;
const CRYPTO_NUMBER_353 = 353;
const CRYPTO_NUMBER_359 = 359;
const CRYPTO_NUMBER_367 = 367;
const CRYPTO_NUMBER_373 = 373;
const CRYPTO_NUMBER_379 = 379;
const CRYPTO_NUMBER_383 = 383;
const CRYPTO_NUMBER_389 = 389;
const CRYPTO_NUMBER_397 = 397;
const CRYPTO_NUMBER_401 = 401;
const CRYPTO_NUMBER_409 = 409;
const CRYPTO_NUMBER_419 = 419;
const CRYPTO_NUMBER_421 = 421;
const CRYPTO_NUMBER_431 = 431;
const CRYPTO_NUMBER_433 = 433;
const CRYPTO_NUMBER_439 = 439;
const CRYPTO_NUMBER_443 = 443;
const CRYPTO_NUMBER_449 = 449;
const CRYPTO_NUMBER_457 = 457;
const CRYPTO_NUMBER_461 = 461;
const CRYPTO_NUMBER_463 = 463;
const CRYPTO_NUMBER_467 = 467;
const CRYPTO_NUMBER_479 = 479;
const CRYPTO_NUMBER_487 = 487;
const CRYPTO_NUMBER_491 = 491;
const CRYPTO_NUMBER_499 = 499;
const CRYPTO_NUMBER_503 = 503;
const CRYPTO_NUMBER_509 = 509;
const CRYPTO_NUMBER_26 = 26;
const CRYPTO_NUMBER_0X4000000 = 0x4000000;
const CRYPTO_NUMBER_0X3FFFFFF = 0x3ffffff;
const CRYPTO_NUMBER_0X7FFF = 0x7fff;
const CRYPTO_NUMBER_15 = 15;
const CRYPTO_NUMBER_0X3FFFFFFF = 0x3fffffff;
const CRYPTO_NUMBER_30 = 30;
const CRYPTO_NUMBER_0X3FFF = 0x3fff;
const CRYPTO_NUMBER_14 = 14;
const CRYPTO_NUMBER_28 = 28;
const CRYPTO_NUMBER_0XFFFFFFF = 0xfffffff;
const CRYPTO_NUMBER_0X1FFF = 0x1fff;
const CRYPTO_NUMBER_52 = 52;
const CRYPTO_NUMBER_9 = 9;
const CRYPTO_NUMBER_36 = 36;
const CRYPTO_NUMBER_256 = 256;
const CRYPTO_NUMBER_16 = 16;
const CRYPTO_NUMBER_4 = 4;
const CRYPTO_NUMBER_8 = 8;
const CRYPTO_NUMBER_32 = 32;
const CRYPTO_NUMBER_0XFF = 0xff;
const CRYPTO_NUMBER_0X80 = 0x80;
const CRYPTO_NUMBER_0XF = 0xf;
const CRYPTO_NUMBER_0XFFFF = 0xffff;
const CRYPTO_NUMBER_0XFFFFFFFF = 0xffffffff;
const CRYPTO_NUMBER_24 = 24;
const CRYPTO_NUMBER_10 = 10;
const CRYPTO_NUMBER_18 = 18;
const CRYPTO_NUMBER_48 = 48;
const CRYPTO_NUMBER_144 = 144;
const CRYPTO_NUMBER_768 = 768;
const CRYPTO_NUMBER_6 = 6;
const CRYPTO_NUMBER_255 = 255;
const CRYPTO_NUMBER_1122926989487 = 1122926989487;
const CRYPTO_NUMBER_65536 = 65536;
const CRYPTO_NUMBER_0X10 = 0x10;
const CRYPTO_NUMBER_1000 = 1000;
const CRYPTO_RUNCOUNT_120 = 120;
// Bits per digit
let dbits;
let bIDB;
let bIDM;
let bIDV;
let bIFP;
let bIFV;
let bIF1;
let bIF2;
let dv = 0;
// JavaScript engine analysis
let canary = 0xdeadbeefcafe;
let jLm = (canary & CRYPTO_NUMBER_0XFFFFFF) === CRYPTO_NUMBER_0XEFCAFE;
let lowprimes = [
    CRYPTO_NUMBER_2, CRYPTO_NUMBER_3, CRYPTO_NUMBER_5, CRYPTO_NUMBER_7, CRYPTO_NUMBER_11, CRYPTO_NUMBER_13, CRYPTO_NUMBER_17, CRYPTO_NUMBER_19,
    CRYPTO_NUMBER_23, CRYPTO_NUMBER_29, CRYPTO_NUMBER_31, CRYPTO_NUMBER_37, CRYPTO_NUMBER_41, CRYPTO_NUMBER_43, CRYPTO_NUMBER_47, CRYPTO_NUMBER_53,
    CRYPTO_NUMBER_59, CRYPTO_NUMBER_61, CRYPTO_NUMBER_67, CRYPTO_NUMBER_71, CRYPTO_NUMBER_73, CRYPTO_NUMBER_79, CRYPTO_NUMBER_83, CRYPTO_NUMBER_89,
    CRYPTO_NUMBER_97, CRYPTO_NUMBER_101, CRYPTO_NUMBER_103, CRYPTO_NUMBER_107, CRYPTO_NUMBER_109, CRYPTO_NUMBER_113, CRYPTO_NUMBER_127, CRYPTO_NUMBER_131,
    CRYPTO_NUMBER_137, CRYPTO_NUMBER_139, CRYPTO_NUMBER_149, CRYPTO_NUMBER_151, CRYPTO_NUMBER_157, CRYPTO_NUMBER_163, CRYPTO_NUMBER_167, CRYPTO_NUMBER_173,
    CRYPTO_NUMBER_179, CRYPTO_NUMBER_181, CRYPTO_NUMBER_191, CRYPTO_NUMBER_193, CRYPTO_NUMBER_197, CRYPTO_NUMBER_199, CRYPTO_NUMBER_211, CRYPTO_NUMBER_223,
    CRYPTO_NUMBER_227, CRYPTO_NUMBER_229, CRYPTO_NUMBER_233, CRYPTO_NUMBER_239, CRYPTO_NUMBER_241, CRYPTO_NUMBER_251, CRYPTO_NUMBER_257, CRYPTO_NUMBER_263,
    CRYPTO_NUMBER_269, CRYPTO_NUMBER_271, CRYPTO_NUMBER_277, CRYPTO_NUMBER_281, CRYPTO_NUMBER_283, CRYPTO_NUMBER_293, CRYPTO_NUMBER_307, CRYPTO_NUMBER_311,
    CRYPTO_NUMBER_313, CRYPTO_NUMBER_317, CRYPTO_NUMBER_331, CRYPTO_NUMBER_337, CRYPTO_NUMBER_347, CRYPTO_NUMBER_349, CRYPTO_NUMBER_353, CRYPTO_NUMBER_359,
    CRYPTO_NUMBER_367, CRYPTO_NUMBER_373, CRYPTO_NUMBER_379, CRYPTO_NUMBER_383, CRYPTO_NUMBER_389, CRYPTO_NUMBER_397, CRYPTO_NUMBER_401, CRYPTO_NUMBER_409,
    CRYPTO_NUMBER_419, CRYPTO_NUMBER_421, CRYPTO_NUMBER_431, CRYPTO_NUMBER_433, CRYPTO_NUMBER_439, CRYPTO_NUMBER_443, CRYPTO_NUMBER_449, CRYPTO_NUMBER_457,
    CRYPTO_NUMBER_461, CRYPTO_NUMBER_463, CRYPTO_NUMBER_467, CRYPTO_NUMBER_479, CRYPTO_NUMBER_487, CRYPTO_NUMBER_491, CRYPTO_NUMBER_499, CRYPTO_NUMBER_503,
    CRYPTO_NUMBER_509
];
let lplim = (1 << CRYPTO_NUMBER_26) / lowprimes[lowprimes.length - 1];
// am: Compute w_j += (x*this_i), propagate carries,
// c is initial carry, returns final carry.
// c < 3*dvalue, x < 2*dvalue, this_i < dvalue
// We need to select the fastest one that works in this environment.
// am1: use a single mult and divide to get the high bits,
// max digit bits should be 26 because
// max internal value = 2*dvalue^2-2*dvalue (< 2^53)
let am1 = (array, i, x, w, j, c, n) => {
    let tempI = i;
    let tempJ = j;
    let tempC = c;
    let tempN = n - 1;
    while (tempN >= 0) {
        let v = x * array[tempI] + w.array[tempJ] + tempC;
        tempC = Math.floor(v / CRYPTO_NUMBER_0X4000000);
        w.array = insertValue(w.array, v & CRYPTO_NUMBER_0X3FFFFFF, tempJ);
        tempI += 1;
        tempJ += 1;
        tempN -= 1;
    }
    return tempC;
};
// am2 avoids a big mult-and-extract completely.
// Max digit bits should be <= 30 because we do bitwise ops
// on values up to 2*hdvalue^2-hdvalue-1 (< 2^31)
let am2 = (array, i, x, w, j, c, n) => {
    let xl = x & CRYPTO_NUMBER_0X7FFF;
    let xh = x >> CRYPTO_NUMBER_15;
    let tempI = i;
    let tempJ = j;
    let tempC = c;
    let tempN = n - 1;
    while (tempN >= 0) {
        let l = array[tempI] & CRYPTO_NUMBER_0X7FFF;
        let h = array[tempI] >> CRYPTO_NUMBER_15;
        let m = xh * l + h * xl;
        l = xl * l + ((m & CRYPTO_NUMBER_0X7FFF) << CRYPTO_NUMBER_15) + w.array[tempJ] + (tempC & CRYPTO_NUMBER_0X3FFFFFFF);
        tempC = (l >>> CRYPTO_NUMBER_30) + (m >>> CRYPTO_NUMBER_15) + xh * h + (tempC >>> CRYPTO_NUMBER_30);
        w.array = insertValue(w.array, l & CRYPTO_NUMBER_0X3FFFFFFF, tempJ);
        tempI += 1;
        tempJ += 1;
        tempN -= 1;
    }
    return tempC;
};
// Alternately, set max digit bits to 28 since some
// browsers slow down when dealing with 32-bit numbers.
let am3 = (array, i, x, w, j, c, n) => {
    let xl = x & CRYPTO_NUMBER_0X3FFF;
    let xh = x >> CRYPTO_NUMBER_14;
    let tempI = i;
    let tempJ = j;
    let tempC = c;
    let tempN = n - 1;
    while (tempN >= 0) {
        let l = array[tempI] & CRYPTO_NUMBER_0X3FFF;
        let h = array[tempI] >> CRYPTO_NUMBER_14;
        let m = xh * l + h * xl;
        l = xl * l + ((m & CRYPTO_NUMBER_0X3FFF) << CRYPTO_NUMBER_14) + w.array[tempJ] + tempC;
        tempC = (l >> CRYPTO_NUMBER_28) + (m >> CRYPTO_NUMBER_14) + xh * h;
        w.array = insertValue(w.array, l & CRYPTO_NUMBER_0XFFFFFFF, tempJ);
        tempI += 1;
        tempJ += 1;
        tempN -= 1;
    }
    return tempC;
};
// This is tailored to VMs with 2-bit tagging. It makes sure
// that all the computations stay within the 29 bits available.
let am4 = (array, i, x, w, j, c, n) => {
    let xl = x & CRYPTO_NUMBER_0X1FFF;
    let xh = x >> CRYPTO_NUMBER_13;
    let tempI = i;
    let tempJ = j;
    let tempC = c;
    let tempN = n - 1;
    while (tempN >= 0) {
        let l = array[tempI] & CRYPTO_NUMBER_0X1FFF;
        let h = array[tempI] >> CRYPTO_NUMBER_13;
        let m = xh * l + h * xl;
        l = xl * l + ((m & CRYPTO_NUMBER_0X1FFF) << CRYPTO_NUMBER_13) + w.array[tempJ] + tempC;
        tempC = (l >> CRYPTO_NUMBER_26) + (m >> CRYPTO_NUMBER_13) + xh * h;
        w.array = insertValue(w.array, l & CRYPTO_NUMBER_0X3FFFFFF, tempJ);
        tempI += 1;
        tempJ += 1;
        tempN -= 1;
    }
    return tempC;
};
let aM;
// am3/28 is best for SM, Rhino, but am4/26 is best for v8.
// Kestrel (Opera 9.5) gets its best result with am4/26.
// IE7 does 9% better with am3/28 than with am4/26.
// Firefox (SM) gets 10% faster with am3/28 than with am4/26.
function setupEngine(fn, bits) {
    aM = fn;
    dbits = bits;
    bIDB = dbits;
    bIDM = (1 << dbits) - 1;
    bIDV = 1 << dbits;
    bIFP = CRYPTO_NUMBER_52;
    bIFV = Math.pow(CRYPTO_NUMBER_2, bIFP);
    bIF1 = bIFP - dbits;
    bIF2 = CRYPTO_NUMBER_2 * dbits - bIFP;
}
// Digit conversions
let bIRM = '0123456789abcdefghijklmnopqrstuvwxyz';
let bIRC = [];
function initBIRC() {
    let rr;
    rr = '0'.charCodeAt(0);
    for (let vv = 0; vv <= CRYPTO_NUMBER_9; ++vv) {
        bIRC = insertValue(bIRC, vv, rr);
        rr += 1;
    }
    rr = 'a'.charCodeAt(0);
    for (let vv = CRYPTO_NUMBER_10; vv < CRYPTO_NUMBER_36; ++vv) {
        bIRC = insertValue(bIRC, vv, rr);
        rr += 1;
    }
    rr = 'A'.charCodeAt(0);
    for (let vv = CRYPTO_NUMBER_10; vv < CRYPTO_NUMBER_36; ++vv) {
        bIRC = insertValue(bIRC, vv, rr);
        rr += 1;
    }
}
class BigInteger {
    // (public) Constructor
    constructor(a, b, c) {
        this.array = [];
        this.t = 0;
        this.s = 0;
        // (public) this & a
        this.opAnd = (x, y) => {
            return x & y;
        };
        // (public) this | a
        this.opOr = (x, y) => {
            return x | y;
        };
        // (public) this ^ a
        this.opXor = (x, y) => {
            return x ^ y;
        };
        // (public) this & ~a
        this.opAndnot = (x, y) => {
            return x & ~y;
        };
        if (a != null) {
            if ('number' === typeof a) {
                this.fromNumber(a, b, c);
            }
            else if (b == null && 'string' !== typeof a) {
                this.fromString(a, CRYPTO_NUMBER_256);
            }
            else {
                this.fromString(a, b);
            }
        }
    }
    // return new, unset BigInteger
    static nbi() {
        return new BigInteger();
    }
    // return bigint initialized to value
    static nbv(i) {
        let r = BigInteger.nbi();
        r.fromInt(i);
        return r;
    }
    int2char(n) {
        return bIRM.charAt(n);
    }
    intAt(s, i) {
        let c = bIRC[s.charCodeAt(i)];
        return c === null ? -1 : c;
    }
    // (protected) copy this to r
    copyTo(r) {
        let i = this.t - 1;
        while (i >= 0) {
            r.array = insertValue(r.array, this.array[i], i);
            i -= 1;
        }
        r.t = this.t;
        r.s = this.s;
    }
    // (protected) set from integer value x, -DV <= x < DV
    fromInt(x) {
        this.t = 1;
        this.s = x < 0 ? -1 : 0;
        if (x > 0) {
            this.array = insertValue(this.array, x, 0);
        }
        else if (x < -1) {
            this.array = insertValue(this.array, x + dv, 0);
        }
        else {
            this.t = 0;
        }
    }
    // (protected) set from string and radix
    fromString(s, b) {
        let k;
        if (b === CRYPTO_NUMBER_16) {
            k = CRYPTO_NUMBER_4;
        }
        else if (b === CRYPTO_NUMBER_8) {
            k = CRYPTO_NUMBER_3;
        }
        else if (b === CRYPTO_NUMBER_256) {
            k = CRYPTO_NUMBER_8; // byte array
        }
        else if (b === CRYPTO_NUMBER_2) {
            k = 1;
        }
        else if (b === CRYPTO_NUMBER_32) {
            k = CRYPTO_NUMBER_5;
        }
        else if (b === CRYPTO_NUMBER_4) {
            k = CRYPTO_NUMBER_2;
        }
        else {
            this.fromRadix(s, b);
            return;
        }
        this.t = 0;
        this.s = 0;
        let i;
        let mi = false;
        let sh = 0;
        if (k === CRYPTO_NUMBER_8) {
            let tempS = s;
            i = tempS.length;
        }
        else {
            i = s.length;
        }
        i -= 1;
        while (i >= 0) {
            let x;
            if (k === CRYPTO_NUMBER_8) {
                x = s[i] & CRYPTO_NUMBER_0XFF;
            }
            else {
                x = this.intAt(s, i);
            }
            if (x < 0) {
                if ((s === null || s === void 0 ? void 0 : s.charAt(i)) === '-') {
                    mi = true;
                }
                continue;
            }
            mi = false;
            if (sh === 0) {
                this.array = insertValue(this.array, x, this.t);
                this.t += 1;
            }
            else if (sh + k > bIDB) {
                this.array = insertValue(this.array, this.array[this.t - 1] | ((x & ((1 << (bIDB - sh)) - 1)) << sh), this.t - 1);
                this.array = insertValue(this.array, x >> (bIDB - sh), this.t);
                this.t += 1;
            }
            else {
                this.array = insertValue(this.array, this.array[this.t - 1] | (x << sh), this.t - 1);
            }
            sh += k;
            if (sh >= bIDB) {
                sh -= bIDB;
            }
            i -= 1;
        }
        if (k === CRYPTO_NUMBER_8 && (s[0] & CRYPTO_NUMBER_0X80) !== 0) {
            this.s = -1;
            if (sh > 0) {
                this.array[this.t - 1] |= ((1 << (bIDB - sh)) - 1) << sh;
            }
        }
        this.clamp();
        if (mi) {
            BigInteger.zero.subTo(this, this);
        }
    }
    // (protected) clamp off excess high words
    clamp() {
        let c = this.s & bIDM;
        while (this.t > 0 && this.array[this.t - 1] === c) {
            this.t -= 1;
        }
    }
    // (public) return string representation in given radix
    toString(b) {
        if (this.s < 0) {
            return '-' + this.negate().toString(b);
        }
        let k;
        if (b === CRYPTO_NUMBER_16) {
            k = CRYPTO_NUMBER_4;
        }
        else if (b === CRYPTO_NUMBER_8) {
            k = CRYPTO_NUMBER_3;
        }
        else if (b === CRYPTO_NUMBER_2) {
            k = 1;
        }
        else if (b === CRYPTO_NUMBER_32) {
            k = CRYPTO_NUMBER_5;
        }
        else if (b === CRYPTO_NUMBER_4) {
            k = CRYPTO_NUMBER_2;
        }
        else {
            return this.toRadix(b);
        }
        let km = (1 << k) - 1;
        let d;
        let m = false;
        let r = '';
        let i = this.t;
        let p = bIDB - ((i * bIDB) % k);
        if (i > 0) {
            i -= 1;
            d = this.array[i] >> p;
            if (p < bIDB && d > 0) {
                m = true;
                r = this.int2char(d);
            }
            while (i >= 0) {
                if (p < k) {
                    d = (this.array[i] & ((1 << p) - 1)) << (k - p);
                    i -= 1;
                    p += bIDB - k;
                    d |= this.array[i] >> p;
                }
                else {
                    p -= k;
                    d = (this.array[i] >> p) & km;
                    if (p <= 0) {
                        p += bIDB;
                        i -= 1;
                    }
                }
                if (d > 0) {
                    m = true;
                }
                if (m) {
                    r += this.int2char(d);
                }
            }
        }
        return m ? r : '0';
    }
    // (public) -this
    negate() {
        let r = BigInteger.nbi();
        BigInteger.zero.subTo(this, r);
        return r;
    }
    // (public) |this|
    abs() {
        return this.s < 0 ? this.negate() : this;
    }
    // (public) return + if this > a, - if this < a, 0 if equal
    compareTo(a) {
        let r = this.s - a.s;
        if (r !== 0) {
            return r;
        }
        let i = this.t;
        r = i - a.t;
        if (r !== 0) {
            return r;
        }
        i -= 1;
        while (i >= 0) {
            r = this.array[i] - a.array[i];
            if (r !== 0) {
                return r;
            }
            i -= 1;
        }
        return 0;
    }
    // returns bit length of the integer x
    nbits(x) {
        let tempX = x;
        let r = 1;
        let t = tempX >>> CRYPTO_NUMBER_16;
        if (t !== 0) {
            tempX = t;
            r += CRYPTO_NUMBER_16;
        }
        t = tempX >> CRYPTO_NUMBER_8;
        if (t !== 0) {
            tempX = t;
            r += CRYPTO_NUMBER_8;
        }
        t = tempX >> CRYPTO_NUMBER_4;
        if (t !== 0) {
            tempX = t;
            r += CRYPTO_NUMBER_4;
        }
        t = tempX >> CRYPTO_NUMBER_2;
        if (t !== 0) {
            tempX = t;
            r += CRYPTO_NUMBER_2;
        }
        t = tempX >> 1;
        if (t !== 0) {
            tempX = t;
            r += 1;
        }
        return r;
    }
    // (public) return the number of bits in "this"
    bitLength() {
        if (this.t <= 0) {
            return 0;
        }
        return bIDB * (this.t - 1) + this.nbits(this.array[this.t - 1] ^ (this.s & bIDM));
    }
    // (protected) r = this << n*DB
    dlShiftTo(n, r) {
        let i = this.t - 1;
        while (i >= 0) {
            r.array = insertValue(r.array, this.array[i], i + n);
            i -= 1;
        }
        i = n - 1;
        while (i >= 0) {
            r.array = insertValue(r.array, 0, i);
            i -= 1;
        }
        r.t = this.t + n;
        r.s = this.s;
    }
    // (protected) r = this >> n*DB
    drShiftTo(n, r) {
        let i = n;
        while (i < this.t) {
            r.array = insertValue(r.array, this.array[i], i - n);
            i += 1;
        }
        r.t = Math.max(this.t - n, 0);
        r.s = this.s;
    }
    // (protected) r = this << n
    lShiftTo(n, r) {
        let bs = n % bIDB;
        let cbs = bIDB - bs;
        let bm = (1 << cbs) - 1;
        let ds = Math.floor(n / bIDB);
        let c = (this.s << bs) & bIDM;
        let i = this.t - 1;
        while (i >= 0) {
            r.array = insertValue(r.array, (this.array[i] >> cbs) | c, i + ds + 1);
            c = (this.array[i] & bm) << bs;
            i -= 1;
        }
        i = ds - 1;
        while (i >= 0) {
            r.array = insertValue(r.array, 0, i);
            i -= 1;
        }
        r.array = insertValue(r.array, c, ds);
        r.t = this.t + ds + 1;
        r.s = this.s;
        r.clamp();
    }
    // (protected) r = this >> n
    rShiftTo(n, r) {
        r.s = this.s;
        let ds = Math.floor(n / bIDB);
        if (ds >= this.t) {
            r.t = 0;
            return;
        }
        let bs = n % bIDB;
        let cbs = bIDB - bs;
        let bm = (1 << bs) - 1;
        r.array = insertValue(r.array, this.array[ds] >> bs, 0);
        for (let i = ds + 1; i < this.t; ++i) {
            r.array = insertValue(r.array, r.array[i - ds - 1] | ((this.array[i] & bm) << cbs), i - ds - 1);
            r.array = insertValue(r.array, this.array[i] >> bs, i - ds);
        }
        if (bs > 0) {
            r.array = insertValue(r.array, r.array[this.t - ds - 1] | ((this.s & bm) << cbs), this.t - ds - 1);
        }
        r.t = this.t - ds;
        r.clamp();
    }
    // (protected) r = this - a
    subTo(a, r) {
        let i = 0;
        let c = 0;
        let m = Math.min(a.t, this.t);
        while (i < m) {
            c += this.array[i] - a.array[i];
            r.array = insertValue(r.array, c & bIDM, i);
            c >>= bIDB;
            i += 1;
        }
        if (a.t < this.t) {
            c -= a.s;
            while (i < this.t) {
                c += this.array[i];
                r.array = insertValue(r.array, c & bIDM, i);
                c >>= bIDB;
                i += 1;
            }
            c += this.s;
        }
        else {
            c += this.s;
            while (i < a.t) {
                c -= a.array[i];
                r.array = insertValue(r.array, c & bIDM, i);
                c >>= bIDB;
                i += 1;
            }
            c -= a.s;
        }
        r.s = c < 0 ? -1 : 0;
        if (c < -1) {
            r.array = insertValue(r.array, bIDV + c, i);
            i += 1;
        }
        else if (c > 0) {
            r.array = insertValue(r.array, c, i);
            i += 1;
        }
        r.t = i;
        r.clamp();
    }
    // (protected) r = this * a, r !== this,a (HAC 14.12)
    // "this" should be the larger one if appropriate.
    multiplyTo(a, r) {
        let x = this.abs();
        let y = a.abs();
        let i = x.t;
        r.t = i + y.t;
        i -= 1;
        while (i >= 0) {
            r.array = insertValue(r.array, 0, i);
            i -= 1;
        }
        for (i = 0; i < y.t; ++i) {
            let value = x.am(0, y.array[i], r, i, 0, x.t);
            r.array = insertValue(r.array, value, i + x.t);
        }
        r.s = 0;
        r.clamp();
        if (this.s !== a.s) {
            BigInteger.zero.subTo(r, r);
        }
    }
    // (protected) r = this^2, r !== this (HAC 14.16)
    squareTo(r) {
        let x = this.abs();
        r.t = CRYPTO_NUMBER_2 * x.t;
        let i = r.t - 1;
        while (i >= 0) {
            r.array = insertValue(r.array, 0, i);
            i -= 1;
        }
        i = 0;
        while (i < x.t - 1) {
            let c = x.am(i, x.array[i], r, CRYPTO_NUMBER_2 * i, 0, 1);
            let value = r.array[i + x.t] + x.am(i + 1, CRYPTO_NUMBER_2 * x.array[i], r, CRYPTO_NUMBER_2 * i + 1, c, x.t - i - 1);
            r.array = insertValue(r.array, value, i + x.t);
            if (r.array[i + x.t] >= bIDV) {
                r.array = insertValue(r.array, r.array[i + x.t] - bIDV, i + x.t);
                r.array = insertValue(r.array, 1, i + x.t + 1);
            }
            i += 1;
        }
        if (r.t > 0) {
            let value = r.array[r.t - 1] + x.am(i, x.array[i], r, CRYPTO_NUMBER_2 * i, 0, 1);
            r.array = insertValue(r.array, value, r.t - 1);
        }
        r.s = 0;
        r.clamp();
    }
    // (protected) divide this by m, quotient and remainder to q, r (HAC 14.20)
    // r !== q, this !== m.  q or r may be null.
    divRemTo(m, q, r) {
        let pm = m.abs();
        if (pm.t <= 0) {
            return;
        }
        let pt = this.abs();
        if (pt.t < pm.t) {
            if (q !== null) {
                q.fromInt(0);
            }
            if (r !== null) {
                this.copyTo(r);
            }
            return;
        }
        if (r === null) {
            r = BigInteger.nbi();
        }
        let y = BigInteger.nbi();
        let ts = this.s;
        let ms = m.s;
        let nsh = bIDB - this.nbits(pm.array[pm.t - 1]); // normalize modulus
        if (nsh > 0) {
            pm.lShiftTo(nsh, y);
            pt.lShiftTo(nsh, r);
        }
        else {
            pm.copyTo(y);
            pt.copyTo(r);
        }
        let ys = y.t;
        let y0 = y.array[ys - 1];
        if (y0 === 0) {
            return;
        }
        let yt = y0 * (1 << bIF1) + (ys > 1 ? y.array[ys - CRYPTO_NUMBER_2] >> bIF2 : 0);
        let d1 = bIFV / yt;
        let d2 = (1 << bIF1) / yt;
        let e = 1 << bIF2;
        let i = r.t;
        let j = i - ys;
        let t = q === null ? BigInteger.nbi() : q;
        y.dlShiftTo(j, t);
        if (r.compareTo(t) >= 0) {
            r.array = insertValue(r.array, 1, r.t);
            r.t += 1;
            r.subTo(t, r);
        }
        BigInteger.one.dlShiftTo(ys, t);
        t.subTo(y, y); // "negative" y so we can replace sub with am later
        while (y.t < ys) {
            y.array = insertValue(y.array, 0, y.t);
            y.t += 1;
        }
        j -= 1;
        while (j >= 0) {
            i -= 1; // Estimate quotient digit
            let qd = r.array[i] === y0 ? bIDM : Math.floor(r.array[i] * d1 + (r.array[i - 1] + e) * d2);
            let value = r.array[i] + y.am(0, qd, r, j, 0, ys);
            r.array = insertValue(r.array, value, i);
            if (r.array[i] < qd) {
                y.dlShiftTo(j, t); // Try it out
                r.subTo(t, r);
                qd -= 1;
                while (r.array[i] < qd) {
                    r.subTo(t, r);
                    qd -= 1;
                }
            }
            j -= 1;
        }
        if (q !== null) {
            r.drShiftTo(ys, q);
            if (ts !== ms) {
                BigInteger.zero.subTo(q, q);
            }
        }
        r.t = ys;
        r.clamp();
        if (nsh > 0) {
            r.rShiftTo(nsh, r);
        } // Denormalize remainder
        if (ts < 0) {
            BigInteger.zero.subTo(r, r);
        }
    }
    // (public) this mod a
    mod(a) {
        let r = BigInteger.nbi();
        this.abs().divRemTo(a, null, r);
        if (this.s < 0 && r.compareTo(BigInteger.zero) > 0) {
            a.subTo(r, r);
        }
        return r;
    }
    invDigit() {
        if (this.t < 1) {
            return 0;
        }
        let x = this.array[0];
        if ((x & 1) === 0) {
            return 0;
        }
        let y = x & CRYPTO_NUMBER_3; // y === 1/x mod 2^2
        y = (y * (CRYPTO_NUMBER_2 - (x & CRYPTO_NUMBER_0XF) * y)) & CRYPTO_NUMBER_0XF; // y === 1/x mod 2^4
        y = (y * (CRYPTO_NUMBER_2 - (x & CRYPTO_NUMBER_0XFF) * y)) & CRYPTO_NUMBER_0XFF; // y === 1/x mod 2^8
        y = (y * (CRYPTO_NUMBER_2 - (((x & CRYPTO_NUMBER_0XFFFF) * y) & CRYPTO_NUMBER_0XFFFF))) & CRYPTO_NUMBER_0XFFFF; // y === 1/x mod 2^16
        // last step - calculate inverse mod DV directly;
        // assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints
        y = (y * (CRYPTO_NUMBER_2 - ((x * y) % bIDV))) % bIDV; // y === 1/x mod 2^dbits
        // we really want the negative inverse, and -DV < y < DV
        return y > 0 ? bIDV - y : -y;
    }
    // (protected) true iff this is even
    isEven() {
        return (this.t > 0 ? this.array[0] & 1 : this.s) === 0;
    }
    // (protected) this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79)
    exp(e, z) {
        if (e > CRYPTO_NUMBER_0XFFFFFFFF || e < 1) {
            return BigInteger.one;
        }
        let r = BigInteger.nbi();
        let r2 = BigInteger.nbi();
        let g = z.convert(this);
        let i = this.nbits(e) - 1 - 1;
        g.copyTo(r);
        while (i >= 0) {
            z.sqrTo(r, r2);
            if ((e & (1 << i)) > 0) {
                z.mulTo(r2, g, r);
            }
            else {
                let t = r;
                r = r2;
                r2 = t;
            }
            i -= 1;
        }
        return z.revert(r);
    }
    // (public) this^e % m, 0 <= e < 2^32
    modPowInt(e, m) {
        let z;
        if (e < CRYPTO_NUMBER_256 || m.isEven()) {
            z = new Classic(m);
        }
        else {
            z = new Montgomery(m);
        }
        return this.exp(e, z);
    }
    // (public)
    clone() {
        let r = BigInteger.nbi();
        this.copyTo(r);
        return r;
    }
    // (public) return value as integer
    intValue() {
        if (this.s < 0) {
            if (this.t === 1) {
                return this.array[0] - bIDV;
            }
            else if (this.t === 0) {
                return -1;
            }
        }
        else if (this.t === 1) {
            return this.array[0];
        }
        else if (this.t === 0) {
            return 0;
        }
        // assumes 16 < DB < 32
        return ((this.array[1] & ((1 << (CRYPTO_NUMBER_32 - bIDB)) - 1)) << bIDB) | this.array[0];
    }
    // (public) return value as byte
    byteValue() {
        return this.t === 0 ? this.s : (this.array[0] << CRYPTO_NUMBER_24) >> CRYPTO_NUMBER_24;
    }
    // (public) return value as short (assumes DB>=16)
    shortValue() {
        return this.t === 0 ? this.s : (this.array[0] << CRYPTO_NUMBER_16) >> CRYPTO_NUMBER_16;
    }
    // (protected) return x s.t. r^x < DV
    chunkSize(r) {
        return Math.floor((Math.LN2 * bIDB) / Math.log(r));
    }
    // (public) 0 if this === 0, 1 if this > 0
    signum() {
        if (this.s < 0) {
            return -1;
        }
        else if (this.t <= 0 || (this.t === 1 && this.array[0] <= 0)) {
            return 0;
        }
        else {
            return 1;
        }
    }
    // (protected) convert to radix string
    toRadix(b) {
        let tempB = b == null ? CRYPTO_NUMBER_10 : b;
        if (this.signum() === 0 || tempB < CRYPTO_NUMBER_2 || tempB > CRYPTO_NUMBER_36) {
            return '0';
        }
        let cs = this.chunkSize(tempB);
        let a = Math.pow(tempB, cs);
        let d = BigInteger.nbv(a);
        let y = BigInteger.nbi();
        let z = BigInteger.nbi();
        let r = '';
        this.divRemTo(d, y, z);
        while (y.signum() > 0) {
            let str = (a + z.intValue()).toString(tempB);
            r = str.slice(1) + r;
            y.divRemTo(d, y, z);
        }
        return z.intValue().toString(tempB) + r;
    }
    // (protected) convert from radix string
    fromRadix(s, b) {
        this.fromInt(0);
        let tempB = b == null ? CRYPTO_NUMBER_10 : b;
        let cs = this.chunkSize(tempB);
        let d = Math.pow(tempB, cs);
        let mi = false;
        let j = 0;
        let w = 0;
        for (let i = 0; i < s.length; ++i) {
            let x = this.intAt(s, i);
            if (x < 0) {
                if (s.charAt(i) === '-' && this.signum() === 0) {
                    mi = true;
                }
                continue;
            }
            w = tempB * w + x;
            j += 1;
            if (j >= cs) {
                this.dMultiply(d);
                this.dAddOffset(w, 0);
                j = 0;
                w = 0;
            }
        }
        if (j > 0) {
            this.dMultiply(Math.pow(tempB, j));
            this.dAddOffset(w, 0);
        }
        if (mi) {
            BigInteger.zero.subTo(this, this);
        }
    }
    // (protected) alternate constructor
    fromNumber(a, b, c) {
        if ('number' === typeof b) {
            // new BigInteger(int,int,RNG)
            if (a < CRYPTO_NUMBER_2) {
                this.fromInt(1);
            }
            else {
                this.fromNumber(a, c);
                if (!this.testBit(a - 1)) {
                    // force MSB set
                    this.bitwiseTo(BigInteger.one.shiftLeft(a - 1), this.opOr, this);
                }
                if (this.isEven()) {
                    this.dAddOffset(1, 0); // force odd
                }
                while (!this.isProbablePrime(b)) {
                    this.dAddOffset(CRYPTO_NUMBER_2, 0);
                    if (this.bitLength() > a) {
                        this.subTo(BigInteger.one.shiftLeft(a - 1), this);
                    }
                }
            }
        }
        else {
            // new BigInteger(int,RNG)
            let x = [];
            let t = a & CRYPTO_NUMBER_7;
            x.length = (a >> CRYPTO_NUMBER_3) + 1;
            b.nextBytes(x);
            if (t > 0) {
                x = insertValue(x, x[0] & ((1 << t) - 1), 0);
            }
            else {
                x = insertValue(x, 0, 0);
            }
            this.fromString(x, CRYPTO_NUMBER_256);
        }
    }
    // (public) convert to bigendian byte array
    toByteArray() {
        let i = this.t;
        let r = [];
        r = insertValue(r, this.s, 0);
        let p = bIDB - ((i * bIDB) % CRYPTO_NUMBER_8);
        let d;
        let k = 0;
        if (i > 0) {
            i -= 1;
            d = this.array[i] >> p;
            if (p < bIDB && d !== (this.s & bIDM) >> p) {
                r = insertValue(r, d | (this.s << (bIDB - p)), k);
                k += 1;
            }
            while (i >= 0) {
                if (p < CRYPTO_NUMBER_8) {
                    d = (this.array[i] & ((1 << p) - 1)) << (CRYPTO_NUMBER_8 - p);
                    i -= 1;
                    p += bIDB - CRYPTO_NUMBER_8;
                    d |= this.array[i] >> p;
                }
                else {
                    p -= CRYPTO_NUMBER_8;
                    d = (this.array[i] >> p) & CRYPTO_NUMBER_0XFF;
                    if (p <= 0) {
                        p += bIDB;
                        i -= 1;
                    }
                }
                if ((d & CRYPTO_NUMBER_0X80) !== 0) {
                    d |= -CRYPTO_NUMBER_256;
                }
                if (k === 0 && (this.s & CRYPTO_NUMBER_0X80) !== (d & CRYPTO_NUMBER_0X80)) {
                    k += 1;
                }
                if (k > 0 || d !== this.s) {
                    r = insertValue(r, d, k);
                    k += 1;
                }
            }
        }
        return r;
    }
    bnEquals(a) {
        return this.compareTo(a) === 0;
    }
    bnMin(a) {
        return this.compareTo(a) < 0 ? this : a;
    }
    bnMax(a) {
        return this.compareTo(a) > 0 ? this : a;
    }
    // (protected) r = this op a (bitwise)
    bitwiseTo(a, op, r) {
        let f;
        let m = Math.min(a.t, this.t);
        for (let i = 0; i < m; ++i) {
            r.array = insertValue(r.array, op(this.array[i], a.array[i]), i);
        }
        if (a.t < this.t) {
            f = a.s & bIDM;
            for (let i = m; i < this.t; ++i) {
                r.array = insertValue(r.array, op(this.array[i], f), i);
            }
            r.t = this.t;
        }
        else {
            f = this.s & bIDM;
            for (let i = m; i < a.t; ++i) {
                r.array = insertValue(r.array, op(f, a.array[i]), i);
            }
            r.t = a.t;
        }
        r.s = op(this.s, a.s);
        r.clamp();
    }
    bnAnd(a) {
        let r = BigInteger.nbi();
        this.bitwiseTo(a, this.opAnd, r);
        return r;
    }
    bnOr(a) {
        let r = BigInteger.nbi();
        this.bitwiseTo(a, this.opOr, r);
        return r;
    }
    bnXor(a) {
        let r = BigInteger.nbi();
        this.bitwiseTo(a, this.opXor, r);
        return r;
    }
    bnAndNot(a) {
        let r = BigInteger.nbi();
        this.bitwiseTo(a, this.opAndnot, r);
        return r;
    }
    // (public) ~this
    bnNot() {
        let r = BigInteger.nbi();
        for (let i = 0; i < this.t; ++i) {
            r.array = insertValue(r.array, bIDM & ~this.array[i], i);
        }
        r.t = this.t;
        r.s = ~this.s;
        return r;
    }
    // (public) this << n
    shiftLeft(n) {
        let r = BigInteger.nbi();
        if (n < 0) {
            this.rShiftTo(-n, r);
        }
        else {
            this.lShiftTo(n, r);
        }
        return r;
    }
    // (public) this >> n
    shiftRight(n) {
        let r = BigInteger.nbi();
        if (n < 0) {
            this.lShiftTo(-n, r);
        }
        else {
            this.rShiftTo(n, r);
        }
        return r;
    }
    // return index of lowest 1-bit in x, x < 2^31
    lbit(x) {
        let tempX = x;
        if (tempX === 0) {
            return -1;
        }
        let r = 0;
        if ((tempX & CRYPTO_NUMBER_0XFFFF) === 0) {
            tempX >>= CRYPTO_NUMBER_16;
            r += CRYPTO_NUMBER_16;
        }
        if ((tempX & CRYPTO_NUMBER_0XFF) === 0) {
            tempX >>= CRYPTO_NUMBER_8;
            r += CRYPTO_NUMBER_8;
        }
        if ((tempX & CRYPTO_NUMBER_0XF) === 0) {
            tempX >>= CRYPTO_NUMBER_4;
            r += CRYPTO_NUMBER_4;
        }
        if ((tempX & CRYPTO_NUMBER_3) === 0) {
            tempX >>= CRYPTO_NUMBER_2;
            r += CRYPTO_NUMBER_2;
        }
        if ((tempX & 1) === 0) {
            r += 1;
        }
        return r;
    }
    // (public) returns index of lowest 1-bit (or -1 if none)
    getLowestSetBit() {
        for (let i = 0; i < this.t; ++i) {
            if (this.array[i] !== 0) {
                return i * bIDB + this.lbit(this.array[i]);
            }
        }
        if (this.s < 0) {
            return this.t * bIDB;
        }
        return -1;
    }
    // return number of 1 bits in x
    cbit(x) {
        let r = 0;
        let tepmX = x;
        while (tepmX !== 0) {
            tepmX &= tepmX - 1;
            r += 1;
        }
        return r;
    }
    // (public) return number of set bits
    bitCount() {
        let r = 0;
        let x = this.s & bIDM;
        for (let i = 0; i < this.t; ++i) {
            r += this.cbit(this.array[i] ^ x);
        }
        return r;
    }
    // (public) true iff nth bit is set
    testBit(n) {
        let j = Math.floor(n / bIDB);
        if (j >= this.t) {
            return this.s !== 0;
        }
        return (this.array[j] & (1 << n % bIDB)) !== 0;
    }
    // (protected) this op (1<<n)
    changeBit(n, op) {
        let r = BigInteger.one.shiftLeft(n);
        this.bitwiseTo(r, op, r);
        return r;
    }
    // (public) this | (1<<n)
    setBit(n) {
        return this.changeBit(n, this.opOr);
    }
    // (public) this & ~(1<<n)
    clearBit(n) {
        return this.changeBit(n, this.opAndnot);
    }
    // (public) this ^ (1<<n)
    flipBit(n) {
        return this.changeBit(n, this.opXor);
    }
    // (protected) r = this + a
    addTo(a, r) {
        let i = 0;
        let c = 0;
        let m = Math.min(a.t, this.t);
        while (i < m) {
            c += this.array[i] + a.array[i];
            r.array = insertValue(r.array, c & bIDM, i);
            c >>= bIDB;
            i += 1;
        }
        if (a.t < this.t) {
            c += a.s;
            while (i < this.t) {
                c += this.array[i];
                r.array = insertValue(r.array, c & bIDM, i);
                c >>= bIDB;
                i += 1;
            }
            c += this.s;
        }
        else {
            c += this.s;
            while (i < a.t) {
                c += a.array[i];
                r.array = insertValue(r.array, c & bIDM, i);
                c >>= bIDB;
                i += 1;
            }
            c += a.s;
        }
        r.s = c < 0 ? -1 : 0;
        if (c > 0) {
            r.array = insertValue(r.array, c, i);
            i += 1;
        }
        else if (c < -1) {
            r.array = insertValue(r.array, bIDV + c, i);
            i += 1;
        }
        r.t = i;
        r.clamp();
    }
    // (public) this + a
    add(a) {
        let r = BigInteger.nbi();
        this.addTo(a, r);
        return r;
    }
    // (public) this - a
    subtract(a) {
        let r = BigInteger.nbi();
        this.subTo(a, r);
        return r;
    }
    // (public) this * a
    multiply(a) {
        let r = BigInteger.nbi();
        this.multiplyTo(a, r);
        return r;
    }
    // (public) this / a
    divide(a) {
        let r = BigInteger.nbi();
        let temp = null;
        this.divRemTo(a, r, temp);
        return r;
    }
    // (public) this % a
    remainder(a) {
        let r = BigInteger.nbi();
        this.divRemTo(a, null, r);
        return r;
    }
    // (public) [this/a,this%a]
    divideAndRemainder(a) {
        let q = BigInteger.nbi();
        let r = BigInteger.nbi();
        this.divRemTo(a, q, r);
        return new Array(q, r);
    }
    // (protected) this *= n, this >= 0, 1 < n < DV
    dMultiply(n) {
        let value = this.am(0, n - 1, this, 0, 0, this.t);
        this.array = insertValue(this.array, value, this.t);
        this.t += 1;
        this.clamp();
    }
    // (protected) this += n << w words, this >= 0
    dAddOffset(n, w) {
        let tempW = w;
        while (this.t <= tempW) {
            this.array = insertValue(this.array, 0, this.t);
            this.t += 1;
        }
        this.array = insertValue(this.array, this.array[tempW] + n, tempW);
        while (this.array[tempW] >= bIDV) {
            this.array = insertValue(this.array, this.array[tempW] - bIDV, tempW);
            tempW += 1;
            if (tempW >= this.t) {
                this.array = insertValue(this.array, 0, this.t);
                this.t += 1;
            }
            this.array = insertValue(this.array, this.array[tempW] + 1, tempW);
        }
    }
    // (public) this^e
    bnPow(e) {
        return this.exp(e, new NullExp());
    }
    // (protected) r = lower n words of "this * a", a.t <= n
    // "this" should be the larger one if appropriate.
    multiplyLowerTo(a, n, r) {
        let i = Math.min(this.t + a.t, n);
        r.s = 0; // assumes a,this >= 0
        r.t = i;
        while (i > 0) {
            i -= 1;
            r.array = insertValue(r.array, 0, i);
        }
        while (i < r.t - this.t) {
            let value = this.am(0, a.array[i], r, i, 0, this.t);
            r.array = insertValue(r.array, value, i + this.t);
            i += 1;
        }
        for (let j = Math.min(a.t, n); i < j; ++i) {
            this.am(0, a.array[i], r, i, 0, n - i);
        }
        r.clamp();
    }
    // (protected) r = "this * a" without lower n words, n > 0
    // "this" should be the larger one if appropriate.
    multiplyUpperTo(a, n, r) {
        let tempN = n - 1;
        r.t = this.t + a.t - tempN;
        let i = r.t - 1;
        r.s = 0; // assumes a,this >= 0
        while (i >= 0) {
            r.array = insertValue(r.array, 0, i);
            i -= 1;
        }
        for (i = Math.max(tempN - this.t, 0); i < a.t; ++i) {
            let value = this.am(tempN - i, a.array[i], r, 0, 0, this.t + i - tempN);
            r.array = insertValue(r.array, value, this.t + i - tempN);
        }
        r.clamp();
        r.drShiftTo(1, r);
    }
    // (public) this^e % m (HAC 14.85)
    modPow(e, m) {
        let i = e.bitLength();
        let k;
        let r = BigInteger.nbv(1);
        let z;
        if (i <= 0) {
            return r;
        }
        else if (i < CRYPTO_NUMBER_18) {
            k = 1;
        }
        else if (i < CRYPTO_NUMBER_48) {
            k = CRYPTO_NUMBER_3;
        }
        else if (i < CRYPTO_NUMBER_144) {
            k = CRYPTO_NUMBER_4;
        }
        else if (i < CRYPTO_NUMBER_768) {
            k = CRYPTO_NUMBER_5;
        }
        else {
            k = CRYPTO_NUMBER_6;
        }
        if (i < CRYPTO_NUMBER_8) {
            z = new Classic(m);
        }
        else if (m.isEven()) {
            z = new Barrett(m);
        }
        else {
            z = new Montgomery(m);
        }
        let g = [];
        let n = CRYPTO_NUMBER_3;
        let k1 = k - 1;
        let km = (1 << k) - 1;
        g = insertBigIntegerValue(g, z.convert(this), 1);
        if (k > 1) {
            let g2 = BigInteger.nbi();
            z.sqrTo(g[1], g2);
            while (n <= km) {
                g = insertBigIntegerValue(g, BigInteger.nbi(), n);
                z.mulTo(g2, g[n - CRYPTO_NUMBER_2], g[n]);
                n += CRYPTO_NUMBER_2;
            }
        }
        let j = e.t - 1;
        let w;
        let is1 = true;
        let r2 = BigInteger.nbi();
        let t;
        i = this.nbits(e.array[j]) - 1;
        while (j >= 0) {
            if (i >= k1) {
                w = (e.array[j] >> (i - k1)) & km;
            }
            else {
                w = (e.array[j] & ((1 << (i + 1)) - 1)) << (k1 - i);
                if (j > 0) {
                    w |= e.array[j - 1] >> (bIDB + i - k1);
                }
            }
            n = k;
            while ((w & 1) === 0) {
                w >>= 1;
                n -= 1;
            }
            i -= n;
            if (i < 0) {
                i += bIDB;
                j -= 1;
            }
            if (is1) {
                // ret == 1, don't bother squaring or multiplying it
                g[w].copyTo(r);
                is1 = false;
            }
            else {
                while (n > 1) {
                    z.sqrTo(r, r2);
                    z.sqrTo(r2, r);
                    n -= CRYPTO_NUMBER_2;
                }
                if (n > 0) {
                    z.sqrTo(r, r2);
                }
                else {
                    t = r;
                    r = r2;
                    r2 = t;
                }
                z.mulTo(r2, g[w], r);
            }
            while (j >= 0 && (e.array[j] & (1 << i)) === 0) {
                z.sqrTo(r, r2);
                t = r;
                r = r2;
                r2 = t;
                i -= 1;
                if (i < 0) {
                    i = bIDB - 1;
                    j -= 1;
                }
            }
        }
        return z.revert(r);
    }
    // (public) gcd(this,a) (HAC 14.54)
    gcd(a) {
        let x = this.s < 0 ? this.negate() : this.clone();
        let y = a.s < 0 ? a.negate() : a.clone();
        if (x.compareTo(y) < 0) {
            let t = x;
            x = y;
            y = t;
        }
        let i = x.getLowestSetBit();
        let g = y.getLowestSetBit();
        if (g < 0) {
            return x;
        }
        if (i < g) {
            g = i;
        }
        if (g > 0) {
            x.rShiftTo(g, x);
            y.rShiftTo(g, y);
        }
        while (x.signum() > 0) {
            i = x.getLowestSetBit();
            if (i > 0) {
                x.rShiftTo(i, x);
            }
            i = y.getLowestSetBit();
            if (i > 0) {
                y.rShiftTo(i, y);
            }
            if (x.compareTo(y) >= 0) {
                x.subTo(y, x);
                x.rShiftTo(CRYPTO_NUMBER_1, x);
            }
            else {
                y.subTo(x, y);
                y.rShiftTo(CRYPTO_NUMBER_1, y);
            }
        }
        if (g > 0) {
            y.lShiftTo(g, y);
        }
        return y;
    }
    // (protected) this % n, n < 2^26
    modInt(n) {
        if (n <= 0) {
            return 0;
        }
        let d = bIDV % n;
        let r = this.s < 0 ? n - 1 : 0;
        if (this.t > 0) {
            if (d === 0) {
                r = this.array[0] % n;
            }
            else {
                let i = this.t - 1;
                while (i >= 0) {
                    r = (d * r + this.array[i]) % n;
                    i -= 1;
                }
            }
        }
        return r;
    }
    // (public) 1/this % m (HAC 14.61)
    modInverse(m) {
        let ac = m.isEven();
        if ((this.isEven() && ac) || m.signum() === 0) {
            return BigInteger.zero;
        }
        let u = m.clone();
        let v = this.clone();
        let a = BigInteger.nbv(1);
        let b = BigInteger.nbv(0);
        let c = BigInteger.nbv(0);
        let d = BigInteger.nbv(1);
        while (u.signum() !== 0) {
            while (u.isEven()) {
                u.rShiftTo(1, u);
                if (ac) {
                    if (!a.isEven() || !b.isEven()) {
                        a.addTo(this, a);
                        b.subTo(m, b);
                    }
                    a.rShiftTo(1, a);
                }
                else if (!b.isEven()) {
                    b.subTo(m, b);
                }
                b.rShiftTo(1, b);
            }
            while (v.isEven()) {
                v.rShiftTo(1, v);
                if (ac) {
                    if (!c.isEven() || !d.isEven()) {
                        c.addTo(this, c);
                        d.subTo(m, d);
                    }
                    c.rShiftTo(1, c);
                }
                else if (!d.isEven()) {
                    d.subTo(m, d);
                }
                d.rShiftTo(1, d);
            }
            if (u.compareTo(v) >= 0) {
                u.subTo(v, u);
                if (ac) {
                    a.subTo(c, a);
                }
                b.subTo(d, b);
            }
            else {
                v.subTo(u, v);
                if (ac) {
                    c.subTo(a, c);
                }
                d.subTo(b, d);
            }
        }
        if (v.compareTo(BigInteger.one) !== 0) {
            return BigInteger.zero;
        }
        if (d.compareTo(m) >= 0) {
            return d.subtract(m);
        }
        if (d.signum() < 0) {
            d.addTo(m, d);
        }
        else {
            return d;
        }
        if (d.signum() < 0) {
            return d.add(m);
        }
        else {
            return d;
        }
    }
    // (public) test primality with certainty >= 1-.5^t
    isProbablePrime(t) {
        let x = this.abs();
        if (x.t === 1 && x.array[0] <= lowprimes[lowprimes.length - 1]) {
            for (let i = 0; i < lowprimes.length; ++i) {
                if (x.array[0] === lowprimes[i]) {
                    return true;
                }
            }
            return false;
        }
        if (x.isEven()) {
            return false;
        }
        let i = 1;
        while (i < lowprimes.length) {
            let m = lowprimes[i];
            let j = i + 1;
            while (j < lowprimes.length && m < lplim) {
                m *= lowprimes[j];
                j += 1;
            }
            m = x.modInt(m);
            while (i < j) {
                if (m % lowprimes[i] === 0) {
                    return false;
                }
                i += 1;
            }
        }
        return x.millerRabin(t);
    }
    // (protected) true if probably prime (HAC 4.24, Miller-Rabin)
    millerRabin(t) {
        let tempT = t;
        let n1 = this.subtract(BigInteger.one);
        let k = n1.getLowestSetBit();
        if (k <= 0) {
            return false;
        }
        let r = n1.shiftRight(k);
        tempT = (tempT + 1) >> 1;
        if (tempT > lowprimes.length) {
            tempT = lowprimes.length;
        }
        let a = BigInteger.nbi();
        for (let i = 0; i < tempT; ++i) {
            a.fromInt(lowprimes[i]);
            let y = a.modPow(r, this);
            if (y.compareTo(BigInteger.one) !== 0 && y.compareTo(n1) !== 0) {
                let j = 1;
                while (j < k && y.compareTo(n1) !== 0) {
                    j += 1;
                    y = y.modPowInt(CRYPTO_NUMBER_2, this);
                    if (y.compareTo(BigInteger.one) === 0) {
                        return false;
                    }
                }
                if (y.compareTo(n1) !== 0) {
                    return false;
                }
            }
        }
        return true;
    }
    am(i, x, w, j, c, n) {
        return aM(this.array, i, x, w, j, c, n);
    }
}
BigInteger.one = BigInteger.nbv(1);
BigInteger.zero = BigInteger.nbv(0);
// Modular reduction using "classic" algorithm
class Classic {
    constructor(m) {
        this.m = m;
    }
    convert(x) {
        if (x.s < 0 || x.compareTo(this.m) >= 0) {
            return x.mod(this.m);
        }
        else {
            return x;
        }
    }
    revert(x) {
        return x;
    }
    reduce(x) {
        x.divRemTo(this.m, null, x);
    }
    sqrTo(x, r) {
        x.squareTo(r);
        this.reduce(r);
    }
    mulTo(x, y, r) {
        x.multiplyTo(y, r);
        this.reduce(r);
    }
}
// Montgomery reduction
class Montgomery {
    constructor(m) {
        this.m = m;
        this.mp = m.invDigit();
        this.mpl = this.mp & CRYPTO_NUMBER_0X7FFF;
        this.mph = this.mp >> CRYPTO_NUMBER_15;
        this.um = (1 << (bIDB - CRYPTO_NUMBER_15)) - 1;
        this.mt2 = CRYPTO_NUMBER_2 * m.t;
    }
    // xR mod m
    convert(x) {
        let r = BigInteger.nbi();
        x.abs().dlShiftTo(this.m.t, r);
        r.divRemTo(this.m, null, r);
        if (x.s < 0 && r.compareTo(BigInteger.zero) > 0) {
            this.m.subTo(r, r);
        }
        return r;
    }
    // x/R mod m
    revert(x) {
        let r = BigInteger.nbi();
        x.copyTo(r);
        this.reduce(r);
        return r;
    }
    // x = x/R mod m (HAC 14.32)
    reduce(x) {
        while (x.t <= this.mt2) {
            // pad x so am has enough room later
            x.array = insertValue(x.array, 0, x.t);
            x.t += 1;
        }
        for (let i = 0; i < this.m.t; ++i) {
            // faster way of calculating u0 = x[i]*mp mod DV
            let j = x.array[i] & CRYPTO_NUMBER_0X7FFF;
            let u0 = (j * this.mpl + (((j * this.mph + (x.array[i] >> CRYPTO_NUMBER_15) * this.mpl) & this.um) << CRYPTO_NUMBER_15)) & bIDM;
            // use am to combine the multiply-shift-add into one call
            j = i + this.m.t;
            let value = x.array[j] + this.m.am(0, u0, x, i, 0, this.m.t);
            x.array = insertValue(x.array, value, j);
            // propagate carry
            while (x.array[j] >= bIDV) {
                x.array = insertValue(x.array, x.array[j] - bIDV, j);
                j += 1;
                x.array = insertValue(x.array, x.array[j] + 1, j);
            }
        }
        x.clamp();
        x.drShiftTo(this.m.t, x);
        if (x.compareTo(this.m) >= 0) {
            x.subTo(this.m, x);
        }
    }
    // r = "x^2/R mod m"; x !== r
    sqrTo(x, r) {
        x.squareTo(r);
        this.reduce(r);
    }
    // r = "xy/R mod m"; x,y !== r
    mulTo(x, y, r) {
        x.multiplyTo(y, r);
        this.reduce(r);
    }
}
class NullExp {
    convert(x) {
        return x;
    }
    revert(x) {
        return x;
    }
    reduce(x) {
        //debugLog('Method not implemented.')
    }
    sqrTo(x, r) {
        x.squareTo(r);
    }
    mulTo(x, y, r) {
        x.multiplyTo(y, r);
    }
}
// Barrett modular reduction
class Barrett {
    constructor(m) {
        // setup Barrett
        this.r2 = BigInteger.nbi();
        this.q3 = BigInteger.nbi();
        BigInteger.one.dlShiftTo(CRYPTO_NUMBER_2 * m.t, this.r2);
        this.mu = this.r2.divide(m);
        this.m = m;
    }
    convert(x) {
        if (x.s < 0 || x.t > CRYPTO_NUMBER_2 * this.m.t) {
            return x.mod(this.m);
        }
        else if (x.compareTo(this.m) < 0) {
            return x;
        }
        else {
            let r = BigInteger.nbi();
            x.copyTo(r);
            this.reduce(r);
            return r;
        }
    }
    revert(x) {
        return x;
    }
    // x = x mod m (HAC 14.42)
    reduce(x) {
        x.drShiftTo(this.m.t - 1, this.r2);
        if (x.t > this.m.t + 1) {
            x.t = this.m.t + 1;
            x.clamp();
        }
        this.mu.multiplyUpperTo(this.r2, this.m.t + 1, this.q3);
        this.m.multiplyLowerTo(this.q3, this.m.t + 1, this.r2);
        while (x.compareTo(this.r2) < 0) {
            x.dAddOffset(1, this.m.t + 1);
        }
        x.subTo(this.r2, x);
        while (x.compareTo(this.m) >= 0) {
            x.subTo(this.m, x);
        }
    }
    // r = x^2 mod m; x !== r
    sqrTo(x, r) {
        x.squareTo(r);
        this.reduce(r);
    }
    // r = x*y mod m; x,y !== r
    mulTo(x, y, r) {
        x.multiplyTo(y, r);
        this.reduce(r);
    }
}
class Arcfour {
    constructor() {
        this.i = 0;
        this.j = 0;
        this.s = [];
    }
    // Initialize arcfour context from key, an array of ints, each from [0..255]
    arc4Init(key) {
        let j = 0;
        let t = 0;
        for (let i = 0; i < CRYPTO_NUMBER_256; ++i) {
            this.s = insertValue(this.s, i, i);
        }
        for (let i = 0; i < CRYPTO_NUMBER_256; ++i) {
            j = (j + this.s[i] + key[i % key.length]) & CRYPTO_NUMBER_255;
            t = this.s[i];
            this.s = insertValue(this.s, this.s[j], i);
            this.s = insertValue(this.s, t, j);
        }
        this.i = 0;
        this.j = 0;
    }
    next() {
        let t;
        this.i = (this.i + 1) & CRYPTO_NUMBER_255;
        this.j = (this.j + this.s[this.i]) & CRYPTO_NUMBER_255;
        t = this.s[this.i];
        this.s = insertValue(this.s, this.s[this.j], this.i);
        this.s = insertValue(this.s, t, this.j);
        return this.s[(t + this.s[this.i]) & CRYPTO_NUMBER_255];
    }
}
// Plug in your RNG constructor here
function prngNewstate() {
    return new Arcfour();
}
// Pool size must be a multiple of 4 and greater than 32.
// An array of bytes the size of the pool will be passed to init()
let rngPsize = CRYPTO_NUMBER_256;
// For best results, put code like
// <body onClick='rngSeedTime();' onKeyPress='rngSeedTime();'>
// in your main HTML document.
let rngState;
let rngPool;
let rngPptr = 0;
// Mix in a 32-bit integer into the pool
function rngSeedInt(x) {
    rngPool[rngPptr] ^= x & CRYPTO_NUMBER_255;
    rngPptr += 1;
    rngPool[rngPptr] ^= (x >> CRYPTO_NUMBER_8) & CRYPTO_NUMBER_255;
    rngPptr += 1;
    rngPool[rngPptr] ^= (x >> CRYPTO_NUMBER_16) & CRYPTO_NUMBER_255;
    rngPptr += 1;
    rngPool[rngPptr] ^= (x >> CRYPTO_NUMBER_24) & CRYPTO_NUMBER_255;
    rngPptr += 1;
    if (rngPptr >= rngPsize) {
        rngPptr -= rngPsize;
    }
}
// Mix in the current time (w/milliseconds) into the pool
function rngSeedTime() {
    // Use pre-computed date to avoid making the benchmark
    // results dependent on the current date.
    rngSeedInt(CRYPTO_NUMBER_1122926989487);
}
// Initialize the pool with junk if needed.
function initRngPool() {
    if (rngPool == null) {
        rngPool = [];
        rngPptr = 0;
        let t;
        while (rngPptr < rngPsize) {
            // extract some randomness from Math.random()
            t = Math.floor(CRYPTO_NUMBER_65536 * Math.random());
            rngPool = insertValue(rngPool, t >>> CRYPTO_NUMBER_8, rngPptr);
            rngPptr += 1;
            rngPool = insertValue(rngPool, t & CRYPTO_NUMBER_255, rngPptr);
            rngPptr += 1;
        }
        rngPptr = 0;
        rngSeedTime();
    }
}
class SecureRandom {
    nextBytes(ba) {
        for (let i = 0; i < ba.length; ++i) {
            ba = insertValue(ba, this.rngGetByte(), i);
        }
    }
    rngGetByte() {
        if (rngState == null) {
            rngSeedTime();
            rngState = prngNewstate();
            rngState.arc4Init(rngPool);
            rngPptr = 0;
            while (rngPptr < rngPool.length) {
                rngPool = insertValue(rngPool, 0, rngPptr);
                rngPptr += 1;
            }
            rngPptr = 0;
        }
        // TODO: allow reseeding after first request
        return rngState.next();
    }
}
// "empty" RSA key constructor
class RsaKey {
    constructor() {
        this.n = null; //default
        this.e = CRYPTO_NUMBER_0;
        this.d = null; //default
        this.p = null; //default
        this.q = null; //default
        this.dmp1 = null; //default
        this.dmq1 = null; //default
        this.coeff = null; //default
    }
    // convert a (hex) string to a bignum object
    parseBigInt(str, r) {
        return new BigInteger(str, r);
    }
    linebrk(s, n) {
        let ret = '';
        let i = 0;
        while (i + n < s.length) {
            ret += s.substring(i, i + n) + '\n';
            i += n;
        }
        return ret + s.substring(i, s.length);
    }
    byte2Hex(b) {
        if (b < CRYPTO_NUMBER_0X10) {
            return '0' + b.toString(CRYPTO_NUMBER_16);
        }
        else {
            return b.toString(CRYPTO_NUMBER_16);
        }
    }
    // PKCS#1 (type 2, random) pad input string s to n bytes, and return a bigint
    pkcs1pad2(s, n) {
        if (n < s.length + CRYPTO_NUMBER_11) {
            //debugLog('Message too long for RSA');
            return null;
        }
        let tempN = n;
        let ba = [];
        let i = s.length - 1;
        while (i >= 0 && tempN > 0) {
            tempN -= 1;
            ba = insertValue(ba, s.charCodeAt(i), tempN);
            i -= 1;
        }
        tempN -= 1;
        ba = insertValue(ba, 0, tempN);
        let rng = new SecureRandom();
        let x = [];
        while (tempN > CRYPTO_NUMBER_2) {
            // random non-zero pad
            x = insertValue(x, 0, 0);
            while (x[0] === 0) {
                rng.nextBytes(x);
            }
            tempN -= 1;
            ba = insertValue(ba, x[0], tempN);
        }
        tempN -= 1;
        ba = insertValue(ba, CRYPTO_NUMBER_2, tempN);
        tempN -= 1;
        ba = insertValue(ba, 0, tempN);
        return new BigInteger(ba);
    }
    // Set the public key fields N and e from hex strings
    setPublic(n, e) {
        if (n.length > 0 && e.length > 0) {
            this.n = this.parseBigInt(n, CRYPTO_NUMBER_16);
            this.e = Number.parseInt(e, CRYPTO_NUMBER_16);
        }
        else {
            //debugLog("Invalid RSA public key");
        }
    }
    // Perform raw public operation on "x": return x^e (mod n)
    doPublic(x) {
        return x.modPowInt(this.e, this.n);
    }
    // Return the PKCS#1 RSA encryption of "text" as an even-length hex string
    encrypt(text) {
        let m = this.pkcs1pad2(text, (this.n.bitLength() + CRYPTO_NUMBER_7) >> CRYPTO_NUMBER_3);
        if (m === null) {
            return null;
        }
        let c = this.doPublic(m);
        if (c === null) {
            return null;
        }
        let h = c.toString(CRYPTO_NUMBER_16);
        if ((h.length & 1) === 0) {
            return h;
        }
        else {
            return '0' + h;
        }
    }
    // Undo PKCS#1 (type 2, random) padding and, if valid, return the plaintext
    pkcs1unpad2(d, n) {
        let b = d.toByteArray();
        let i = 0;
        while (i < b.length && b[i] === 0) {
            i += 1;
        }
        if (b.length - i !== n - 1 || b[i] !== CRYPTO_NUMBER_2) {
            return null;
        }
        i += 1;
        while (b[i] !== 0) {
            i += 1;
            if (i >= b.length) {
                return null;
            }
        }
        let ret = '';
        i += 1;
        while (i < b.length) {
            ret += String.fromCharCode(b[i]);
            i += 1;
        }
        return ret;
    }
    // Set the private key fields N, e, and d from hex strings
    setPrivate(n, e, d) {
        if (n.length > 0 && e.length > 0) {
            this.n = this.parseBigInt(n, CRYPTO_NUMBER_16);
            this.e = Number.parseInt(e, CRYPTO_NUMBER_16);
            this.d = this.parseBigInt(d, CRYPTO_NUMBER_16);
        }
        else {
            //debugLog("Invalid RSA private key");
        }
    }
    // Set the private key fields N, e, d and CRT params from hex strings
    setPrivateEx(n, e, d, p, q, dp, dq, c) {
        if (n.length > 0 && e.length > 0) {
            this.n = this.parseBigInt(n, CRYPTO_NUMBER_16);
            this.e = Number.parseInt(e, CRYPTO_NUMBER_16);
            this.d = this.parseBigInt(d, CRYPTO_NUMBER_16);
            this.p = this.parseBigInt(p, CRYPTO_NUMBER_16);
            this.q = this.parseBigInt(q, CRYPTO_NUMBER_16);
            this.dmp1 = this.parseBigInt(dp, CRYPTO_NUMBER_16);
            this.dmq1 = this.parseBigInt(dq, CRYPTO_NUMBER_16);
            this.coeff = this.parseBigInt(c, CRYPTO_NUMBER_16);
        }
        else {
            //debugLog("Invalid RSA private key");
        }
    }
    // Generate a new random private key B bits long, using public expt E
    generate(b, e) {
        let rng = new SecureRandom();
        let qs = b >> 1;
        this.e = Number.parseInt(e, CRYPTO_NUMBER_16);
        let ee = new BigInteger(e, CRYPTO_NUMBER_16);
        while (true) {
            while (true) {
                this.p = new BigInteger(b - qs, 1, rng);
                if (this.p.subtract(BigInteger.one).gcd(ee).compareTo(BigInteger.one) === 0 && this.p.isProbablePrime(CRYPTO_NUMBER_10)) {
                    break;
                }
            }
            while (true) {
                this.q = new BigInteger(qs, 1, rng);
                if (this.q.subtract(BigInteger.one).gcd(ee).compareTo(BigInteger.one) === 0 && this.q.isProbablePrime(CRYPTO_NUMBER_10)) {
                    break;
                }
            }
            if (this.p.compareTo(this.q) <= 0) {
                let t = this.p;
                this.p = this.q;
                this.q = t;
            }
            let p1 = this.p.subtract(BigInteger.one);
            let q1 = this.q.subtract(BigInteger.one);
            let phi = p1.multiply(q1);
            if (phi.gcd(ee).compareTo(BigInteger.one) === 0) {
                this.dmp1 = this.d.mod(p1);
                this.dmq1 = this.d.mod(q1);
                this.n = this.p.multiply(this.q);
                this.d = ee.modInverse(phi);
                this.coeff = this.q.modInverse(this.p);
                break;
            }
        }
    }
    // Perform raw private operation on "x": return x^d (mod n)
    doPrivate(x) {
        if (this.p === null || this.q === null) {
            return x.modPow(this.d, this.n);
        }
        // TODO: re-calculate any missing CRT params
        let xp = x.mod(this.p).modPow(this.dmp1, this.p);
        let xq = x.mod(this.q).modPow(this.dmq1, this.q);
        while (xp.compareTo(xq) < 0) {
            xp = xp.add(this.p);
        }
        return xp
            .subtract(xq)
            .multiply(this.coeff)
            .mod(this.p)
            .multiply(this.q)
            .add(xq);
    }
    // Return the PKCS#1 RSA decryption of "ctext".
    // "ctext" is an even-length hex string and the output is a plain string.
    decrypt(ctext) {
        let c = this.parseBigInt(ctext, CRYPTO_NUMBER_16);
        let m = this.doPrivate(c);
        if (m === null) {
            return null;
        }
        return this.pkcs1unpad2(m, (this.n.bitLength() + CRYPTO_NUMBER_7) >> CRYPTO_NUMBER_3);
    }
}
let nValue = 'a5261939975948bb7a58dffe5ff54e65f0498f9175f5a09288810b8975871e99af3b5dd94057b0fc07535f5f97444504fa35169d461d0d30cf0192e307727c065168c788771c561a9400fb49175e9e6aa4e23fe11af69e9412dd23b0cb6684c4c2429bce139e848ab26d0829073351f4acd36074eafd036a5eb83359d2a698d3';
let eValue = '10001';
let dValue = '8e9912f6d3645894e8d38cb58c0db81ff516cf4c7e5a14c7f1eddb1459d2cded4d8d293fc97aee6aefb861859c8b6a3d1dfe710463e1f9ddc72048c09751971c4a580aa51eb523357a3cc48d31cfad1d4a165066ed92d4748fb6571211da5cb14bc11b6e2df7c1a559e6d5ac1cd5c94703a22891464fba23d0d965086277a161';
let pValue = 'd090ce58a92c75233a6486cb0a9209bf3583b64f540c76f5294bb97d285eed33aec220bde14b2417951178ac152ceab6da7090905b478195498b352048f15e7d';
let qValue = 'cab575dc652bb66df15a0359609d51d1db184750c00c6698b90ef3465c99655103edbf0d54c56aec0ce3c4d22592338092a126a0cc49f65a4a30d222b411e58f';
let dmp1Value = '1a24bca8e273df2f0e47c199bbf678604e7df7215480c77c8db39f49b000ce2cf7500038acfff5433b7d582a01f1826e6f4d42e1c57f5e1fef7b12aabc59fd25';
let dmq1Value = '3d06982efbbe47339e1f6d36b1216b8a741d410b0c662f54f7118b27b9a4ec9d914337eb39841d8666f3034408cf94f5b62f11c402fc994fe15a05493150d9fd';
let coeffValue = '3a3e731acd8960b7ff9eb81a7ff93bd1cfa74cbd56987db58b4594fb09c09084db1734c8143f98b602b981aaa9243ca28deb69b5b280ee8dcee0fd2625e53250';
let text = 'The quick brown fox jumped over the extremely lazy frog! ' + 'Now is the time for all good men to come to the party.';
let encrypted;
function encrypt() {
    let RSA = new RsaKey();
    RSA.setPublic(nValue, eValue);
    RSA.setPrivateEx(nValue, eValue, dValue, pValue, qValue, dmp1Value, dmq1Value, coeffValue);
    encrypted = RSA.encrypt(text);
}
function decrypt() {
    let RSA = new RsaKey();
    RSA.setPublic(nValue, eValue);
    RSA.setPrivateEx(nValue, eValue, dValue, pValue, qValue, dmp1Value, dmq1Value, coeffValue);
    let decrypted = RSA.decrypt(encrypted);
    if (decrypted !== text) {
        // debugLog("Crypto operation failed");
    }
}
/*
 * @State
 * @Tags Jetstream2
 */
class Benchmark {
    /*
     * @Setup
     */
    cryptoSetup() {
        initBIRC();
        initRngPool();
        setupEngine(am3, CRYPTO_NUMBER_28);
    }
    /*
     * @Benchmark
     */
    runIteration() {
        encrypt();
        decrypt();
    }
}
function cryptoRunIteration() {
    let benchmark = new Benchmark();
    let setupStart = Date.now();
    benchmark.cryptoSetup();
    let setupEnd = Date.now();
    //debugLog("setupTime: " + String(setupEnd - setupStart) + "ms");
    let runTimes = [];
    let runStart = Date.now();
    for (let index = 0; index < CRYPTO_RUNCOUNT_120; index++) {
        let start = Date.now();
        benchmark.runIteration();
        let end = Date.now();
        let runtime = end - start;
        runTimes.push(runtime);
        // debugLog("onceRunTime: " + String(runtime) + "ms");
    }
    let endTime = Date.now();
    // debugLog("runTime: " + String(endTime - runStart) + "ms");
    console.log('crypto: ms = ' + String(endTime - setupStart));
}
function debugLog(str) {
    let isLog = false;
    if (isLog) {
        console.log(str);
    }
}
function insertBigIntegerValue(array, value, i) {
    let arr = array;
    if (i < arr.length) {
        arr[i] = value;
    }
    else {
        const surplus = i - arr.length;
        const surplusArr = new Array(surplus + 1).fill(null);
        arr = arr.concat(surplusArr);
        arr[i] = value;
    }
    return arr;
}
function insertValue(array, value, i) {
    let arr = array;
    if (i < arr.length) {
        arr[i] = value;
    }
    else {
        const surplus = i - arr.length;
        const surplusArr = new Array(surplus + 1).fill(null);
        arr = arr.concat(surplusArr);
        arr[i] = value;
    }
    return arr;
}
cryptoRunIteration();
